The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Chapter 7
The Design of Twofish

7.1 The Round Structure

An n-bit block cipher with a k-bit key uses its key to select among 2k possible different permutations on the 2n. possible inputs/outputs to the cipher. This can be imagined as an enormous (virtual) codebook; each possible n-bit plaintext block leads to only one possible n-bit ciphertext block under a given key. Data is encrypted in n-bit chunks, with each n-bit chunk's encryption independent of other encryptions. This can be contrasted with a stream cipher, where different parts of the message are treated differently. The goal for a block cipher is to be impossible in practice to distinguish from a random permutation family on n-bit blocks.

DES is a 64-bit cipher, and most block ciphers in the literature are also 64-bit ciphers; AES, on the other hand, requires a 128-bit block cipher.

A product cipher (sometimes called an iterative block cipher) is a block cipher made by iterating a fairly simple round function many times, each time with its own key. Thus, a 4-round product cipher would look like

EK(X) = RK3(RK2(RK1(RK0(X))))

where K0...3 are functions of K.

Each round function, RK(), is actually a weak block cipher. It implements the basic Shannon principles of encryption, confusion and diffusion [Sha49], and can be viewed as a key-dependent transformation of plaintext into ciphertext. It is weak in the sense that if an attacker knows much about the plaintext (such as simple plaintext statistics), he can quickly break the round function and recover its round key.

Even a very weak round function is resistant to attack when the sequence of inputs to the function is random and unknown to the attacker. Iterating the round function many times makes the input to the last round very hard for an attacker to guess; this prevents the attacker from being able to attack the last round, and thus prevents him from attacking the cipher as a whole. An increased number of rounds means a decrease in the throughput of a cipher, but an attack effective against an n-round version of a particular algorithm might be ineffective against an n + 1-round version. Some of the best cipher analysis shows how to break reduced-round variants of the design and why each attack cannot be extended to a greater number of rounds.


Fig. 7.1.  A Simple SP-network Construction

7.1.1 Common Block Cipher Structures

All well-known block ciphers use this iterated round structure, and given the number of different algorithms that have been proposed over the years, there are surprisingly few round-function structures.

SP Networks. These were named by Horst Feistel [Fei73, FNS75], although the ideas are much older. “SP” stands for “substitution-permutation,” and one round of an SP-network consists of a substitution layer followed by a permutation layer. These two layers are meant to capture C. Shannon’s fundamental notions in cipher design of confusion and diffusion [Sha49]. The substitution layer confuses the statistics of the input by breaking it up into smaller pieces and performing substitutions on those pieces. The permutation layer diffuses the statistics of the input by rearranging the bits output from the substitution layer, each of which should be a function of more than one input bit. Figure 7.1 gives a simple SP-network construction (which is not secure).

SP-networks have been well-studied in the cryptographic literature; examples of SP-network designs are SAFER [Mas94], Shark [RDP+96], and Square [DKR97].1 Rotor machines can be viewed as SP networks: the rotor is a substitution layer, and the key-dependent stepping of the rotor is the permutation.


1 See also [HT94b].

Feistel Networks. These were invented by Horst Feistel [FNS75] in his design of Lucifer[Fei73]. The fundamental building block of a Feistel network is the F function, a key-dependent mapping of an input string onto an output string. An F function is always non-linear and possibly non-surjective2


2 A non-surjective F function is one in which not all outputs in the output space can occur.

F : {0,1}n/2 × {0, 1}k → {0, 1}n/2

where n is the block size of the Feistel network, and F is a function taking n/2 bits of the block and k bits of a key as input, and producing an output of length n/2 bits. In each round, the “source block” is the input to F, and the output of F is XORed with the “target block,” after which these two blocks swap places for the next round. Feistel networks are the most studied block cipher structure, and are the basis for most of the algorithms proposed in the literature.


Fig. 7.2.  A 3-round Feistel Network

Figure 7.2 shows a 3-round Feistel network. Here (PL, PR) is the plaintext, (CL, CR) is the ciphertext, (L1, R1) and (L2, R2) are intermediate values, and K1, K2, and K3 are round-dependent subkeys.

In order to decrypt the ciphertext (CL, CR) one starts at the tail end of the network and works backwards. It is important to understand that data flows the same direction through F even during decryption and that the reversibility of the network comes from the property that α ⊕ α = 0 for any α. This is easy to see if we compute the ciphertext as a function of the plaintext:

(L1, R1) = (PL, PR ⊕ F(PL))
(L2, R2) = (R1, L1F(R1))
(CL, CR) = (R2, L2F(R2))

Then reversing the network we find:

(L2, R2) = (CR ⊕ F(CL), CL)
(L1, R1) = (R2F(L2), L2)
(PL, PR) = (R1F(L1), L1)


Fig. 7.3.  An Incomplete 2-round Feistel Network

Incomplete Feistel Networks. This is a variant of the Feistel network where the F-function has an input and output size that is some fraction of n other than n/2. Skipjack, for example, has an F-function whose input and output is one-quarter the block size [NSA98]:

F : {0,1}n/4 × {0, 1}k → {0, 1}n/4

Figure 7.3 shows a 2-round variant of an incomplete Feistel network whose F-function also has an input and output of one-quarter the block size. In each round, the source block is the input into F, and is XORed with the target block; the other bits are unused in the round (hence the name “incomplete Feistel network”).3 Then, the subblocks are rotated among each other, so that each subblock becomes the source and target in subsequent rounds. The first incomplete Feistel networks in the literature were Khufu and Khafre [Mer91], although their similarities to shift-register-based stream ciphers (common in military cryptographic hardware) make it likely that there is a significant amount of classified literature on their design and analysis.


3A taxonomy of these Feistel-network variants can be found in [SK96].

Source-heavy Feistel Networks. In this variant of the Feistel network, the source and target blocks are of different size, with the source block larger than the target block. Both RC2 [Riv97] and MacGuffin [BS95] have a 48-by-16-bit source-heavy structure; the F-function takes a 48-bit input and produces a 16-bit output. The underlying block cipher in MD4 [Riv91] and MD5 [Riv92] are 96-by-32-bit structures. SHA-1 [NIST93] is a 128-by-32-bit structure. Figure 7.4 shows a source-heavy 2-round Feistel network.


Previous Table of Contents Next